""" 全排列，回溯算法，递归很烦 """
from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = []
    n = len(nums)
    def backtrack(first = 0):
        if first == n:
            res.append(nums[:])
        for i in range(first, n): #遍历
            nums[first],nums[i] = nums[i], nums[first]
            backtrack(first+1)
            nums[first], nums[i] = nums[i], nums[first]
    backtrack()
    return res

nums = [1,2,3,4,5]
print(permute(nums))
